from typing import List


class Solution:
    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
        total = sum(sweetness)

        if k == 0:
            return total

        def enough(num):
            res = 0
            now = 0
            for sweet in sweetness:
                now += sweet
                if now >= num:
                    now = 0
                    res += 1
            return res >= (k + 1)

        left, right = 0, total // k
        while left < right:
            mid = (left + right) // 2 + 1
            if not enough(mid):
                right = mid - 1
            else:
                left = mid
        return left


if __name__ == "__main__":
    # 6
    print(Solution().maximizeSweetness(sweetness=[1, 2, 3, 4, 5, 6, 7, 8, 9], k=5))

    # 1
    print(Solution().maximizeSweetness(sweetness=[5, 6, 7, 8, 9, 1, 2, 3, 4], k=8))

    # 5
    print(Solution().maximizeSweetness(sweetness=[1, 2, 2, 1, 2, 2, 1, 2, 2], k=2))
